1. Field of the Invention
This invention relates to a buffer memory control system, and more particularly to a buffer memory control device in which, in the determination of priority of unit data blocks planted in a buffer memory, priority levels of set blocks, each including a predetermined number of unit data blocks, are determined and, at the same time, priority levels of the unit data blocks making up each set block are determined, thereby to decrease the number of bits necessary for the priority processing.
2. Description of the Prior Art
In general, a data processor having a buffer memory is designed to access a tag portion of the buffer memory to detect whether or not desired information has been planted in a data portion of the buffer memory. A data processor having a main memory and a buffer memory is disclosed, for example, in U.S. Pat. No. 3,588,829. Since only a limited number of unit data blocks are planted in the data portion of the buffer memory, a priority circuit is provided and, for example, in the case of the set associative system, priority levels of unit data blocks of a predetermined number of sets planted for each column are determined whereby to efficiently plant the unit data blocks in the data portion. Let it be assumed, for example, that the highest priority is given to the latest accessed one of the unit data blocks of the predetermined number of sets and that the lowest priority is given to the earliest accessed unit data block. (This is called the LRU algorithm.) In the case where it is necessary to transfer a new unit data block to the buffer memory from another memory (main memory), the unit data block given the lowest priority is assigned as a block to be replaced with the new unit data block and is driven out from the buffer memory, and then the new unit data block is transferred to the buffer memory.
In such priority processing according to the prior art, for example, if the set number of the buffer memory is 2, that is, if the number of unit data blocks which can be planted on the buffer memory is 2, one bit is required for determining two priority relationships. That is, either one of the two set has priority over the other depending upon whether the bit is "1" or "0". Similarly, in the case of the number of sets planted on the buffer memory being 4, the number of bits required is 6 in all which are respectively indicative of the priority relationships between first and second sets, between first and third sets, between first and fourth sets, between the second and third sets, between the second and fourth sets and between the third and fourth sets. In the cases of the number of sets being 8, 16 and 32, the required number of bits is 28, 120 and 496, respectively. In other words, if the number of sets is taken as x, the required number of bits is given by x(x-1)/2. Since the number of pairs of sets selected from the set number x is x(x-1)/2 and since either one of the two sets of each pair is given priority over the other depending upon whether one bit is "1" or "0", the above relationship equation is obtained.
However, it is generally believed that the number of bits usable within practice is 28 at the largest, and priority processing for a relatively large capacity buffer memory having more than 16 sets requires a very large amount of hardware and is regarded as difficult from the technical point of view, too.